package com.lh.nk;

import java.util.PriorityQueue;

/**
 * @author: linghao
 * @since: 2023/1/29
 *
 * 描述
 * 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
 *
 * 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
 */
public class 寻找第K大NC88 {

    //利用优先队列（默认升序排序），最小堆,根最小
    public int findKth(int[] a, int n, int K) {
        // write code here
        PriorityQueue<Integer> queue = new PriorityQueue<>(K);
        for(int i:a){
            if(queue.size()<K){
                queue.add(i);
            }else{
                if(i>queue.peek()){  //大的里面挑出小的剔除，放入更大的
                    queue.poll();
                    queue.add(i);
                }
            }
        }
        return queue.isEmpty() ? 0:queue.peek();
    }
}
